package linkedList;

/**
 * 环形链表 -141
 *
 * @author yyz
 * @create 2023-11-25 13:56
 */
public class 环形链表 {
    public boolean hasCycle(ListNode head) {
        ListNode p1 = head;// 兔
        ListNode p2 = head;// 龟
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p2 = p2.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 环形链表 II -142
     *
     * @param head 链表
     * @return 环的入口
     */
    public ListNode detectCycle(ListNode head) {
        ListNode p1 = head;// 兔
        ListNode p2 = head;// 龟
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p2 = p2.next;
            if (p1 == p2) {
                //找入口
                p2 = head;
                while (true) {
                    if (p1 == p2) {
                        return p1;
                    }
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        // 构造一个带环链表
        ListNode n12 = new ListNode(12, null);
        ListNode n11 = new ListNode(11, n12);
        ListNode n10 = new ListNode(10, n11);
        ListNode n9 = new ListNode(9, n10);
        ListNode n8 = new ListNode(8, n9);
        ListNode n7 = new ListNode(7, n8);
        ListNode n6 = new ListNode(6, n7);
        ListNode n5 = new ListNode(5, n6);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);

        n12.next = n1;
        System.out.println(new 环形链表().detectCycle(n1).val);
    }
}
